<!DOCTYPE html>
<html lang="en">
    <head>
        <meta charset="UTF-8" />
        <meta http-equiv="X-UA-Compatible" content="IE=edge" />
        <meta name="viewport" content="width=device-width, initial-scale=1.0" />
        <title>动态规划</title>
    </head>
    <body></body>
    <script>
        // 解决重复计算的方法：1.带有备忘录的递归 2.自底向上
        // 斐波那契数列
        function fib_dg(n) {
            var arr = [0, 1];
            var i = 2;
            // 我们定义一个数组， arr[i] 表示 前 i 个的和
            while (n > 1 && i <= n) {
                arr[i] = arr[i - 1] + arr[i - 2];
                i++;
            }

            if (n === 0) {
                return 0;
            } else if (n === 1) {
                return 1;
            } else {
                return arr[n];
            }
        }

        // 这个是传统的递归写法，我们可以尝试对比下性能
        // function fib_dg(n) {
        //     if (n === 0) {
        //         return 0;
        //     } else if (n === 1) {
        //         return 1;
        //     } else {
        //         return fib_dg(n - 1) + fib_dg(n - 2);
        //     }
        // }

        // 可以说性能绝对是完虐
        console.log(fib_dg(999));
    </script>
</html>
